The background description provided herein is for the purpose of generally presenting the context of the disclosure. Unless otherwise indicated herein, the materials described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
Deflate is a commonly used compression algorithm, originally specified by The Internet Engineering Task Force, Request For Comments, 1951, first published in May, 1996. Deflate combines LZ77 and Huffman encoding. LZ77 compresses data by replacing subsequent occurrences of repeated data with a length, distance (“[Len, D]”) token. In the [Len, D] token, length (“Len”) refers to the number of bits at the current location which are to be supplied by earlier bits; while distance (“D”) states how much before the current location the supplied bits occur. In LZ77 encoding, bits can be encoded as a literal, as a length, or as a distance. Because D always follows Len, if a Len is decoded, bit(s) immediately following the Len value must define a D value. Huffman encoding replaces repeating symbols with codes. In the Huffman encoding process, more commonly occurring symbols are assigned shorter codes and less commonly occurring symbols are assigned longer codes. Huffman codes can have a variable bit length, from 2 to 15 bits.
In a deflate encoded bitstream, a header contains all necessary information to recreate the following two Huffman tables: a first table for decoding literals and length values, and a second table for decoding distance values. Deflate decoding proceeds in a serial manner because there is no way to know how long a current code is, and when the next code in the bitstream begins, until the current code is decoded. As a consequence, deflate decoding introduces non-trivial latency into a communication session.
Encoding schemes exist which use a fixed bit rate, though they typically do not offer the same compression benefits. Other encoding schemes offer better compression (typically with variable bit rates), but typically only with even greater latency or greater processing cost, compared to deflate.
If a method and apparatus can be designed to reduce deflate decoding latency, deflate could be used more widely.